# 填充每个节点的下一个右侧节点指针： https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/

class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next


from collections import deque
# 1. 层序遍历很简单
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        """
            层序遍历，很简单，空间复杂度不是常量级别
        """
        if not root: return root
        
        d = deque()
        d.append(root)
        while d :
            n = len(d)
            for i in range(n):
                node = d.popleft()
                if i != n - 1: node.next = d[0]
                
                if node.left: d.append(node.left)
                if node.right: d.append(node.right)
            
        return root


# 双指针，代替层序遍历中队列的功能，空间复杂度O(1)
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        """
            代码优化： 通过层序遍历的写法， 我们知道，队列的作用是 使当前节点知道自己右侧的节点是谁。 那么 我们既然有了 next 指针, 就可以利用next指针，完成队列的功能。

            双指针解法：
            1. 指针（1），依次遍历，当前节点的 左子节点， 也就是每层的最左边节点
            2. 指针（2），分别通过next指针遍历每层的节点。设当前节点为 cur, 遍历时，每个节点完成如下操作
                cur.left.next = cur.right
                if cur.next:
                    cur.right.next = cur.next.left

            # 注意： 题目的描述，一定是一颗满二叉树，或者是最后一层少一个 右子节点
        """
        if not root: return root
        node = root
        # 1. 遍历左子节点
        while node.left:
            cur = node
            while cur:
                cur.left.next = cur.right
                if cur.next:
                    cur.right.next = cur.next.left

                cur = cur.next

            node = node.left
        
        return root



# 还可以使用深度优先遍历， 不是很好想感觉，虽然过程核心是一样的